package com.example.programmerinterview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 面试题 17.11. 单词距离
 * 有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
 * <p>
 * 示例：
 * <p>
 * 输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
 * 输出：1
 * <p>
 * 思路：遍历一边，当碰到目标字符串时入队列，最后进行比较取最优值
 */
public class FindClosest {
    public static int findClosest2(String[] words, String word1, String word2) {
        int n = words.length;
        Map<String, List<Integer>> map = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault(words[i], new ArrayList<>());
            list.add(i);
            map.put(words[i], list);
        }
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int min = Integer.MAX_VALUE;
        for (int i : list1) {
            for (int j : list2) {
                min = Math.min(Math.abs(i - j), min);
                if (min == 0) return min;
            }
        }
        return min;
    }

    /**
     * map简化版
     */
    public static int findClosest(String[] words, String word1, String word2) {
        int n = words.length;
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (words[i] == word1) list1.add(i);
            if (words[i] == word2) list2.add(i);
        }
        int min = Integer.MAX_VALUE;
        for (int i : list1) {
            for (int j : list2) {
                min = Math.min(Math.abs(i - j), min);
            }
        }
        return min;
    }

    public static void main(String[] args) {
        String[] strings = {"I", "am", "a", "student", "from", "a", "university", "in", "a", "citystudent", "from", "a", "university",};
        System.out.println(FindClosest.findClosest(strings, "university", "citystudent"));
        System.out.println(FindClosest.findClosest2(strings, "university", "citystudent"));
    }
}
